package com.practice.recursive;

import java.util.Arrays;

public class RepetitionPermute {
	public void permute(String a) {
		char[] c = a.toCharArray();
		Arrays.sort(c);
		permute("", c, 0);
	}
	
	private void permute(String s, char[] c, int begin) {
		if (begin == c.length) {
			System.out.println(s);
			return;
		}
		
		int end = begin+1;
		while (end < c.length && c[end]==c[begin]) end++;
		int len = end - begin;
		
		permute(s, c[begin], len, 0, c, end);
	}
	
	private void permute(String s, char ch, int len, int start, char[] c, int begin) {
		if (len == 0) {
			permute(s, c, begin);
			return;
		}
		
		String fill = "";
		for (int i=0; i<len; i++) {
			fill += ch;
			for (int j=start; j<=s.length(); j++) {
				permute(s.substring(0, j) + fill + s.substring(j), ch, len-i-1, j+i+2, c, begin);
			}
		}
	}
	
	public static void main(String[] args) {
		new RepetitionPermute().permute("AAABB");
	}
}
